package dataStructure.study.linkedList;

/**
 * Author: shangsf
 * Date: 2021/3/28 17:56
 * Description:
 */
public class LinkedListAlgorithm {

    /**
     * 单链表反转:
     */
    public <T> Node<T> reverse(Node<T> head){
        if(head==null||head.next==null){
            return head;
        }
        Node<T> prev=null;
        Node<T> curr=head;
        Node<T> next=head.next;
        while (next!=null){
            if(prev==null){
                curr.next=null;
            }
            prev=curr;
            curr=next;
            next=next.next;

            curr.next=prev;
        }
        return curr;
    }

    /**
     * 单链表反转1：递归反转
     */
    public <T> Node<T> reverse1(Node<T> node){
        // node是前一结点，node.next是当前结点，newNode是反转后新链表的头结点
        if(node==null||node.next==null){
            return node;//若为空链或者当前结点在尾结点，则直接还回
        }
        Node<T> newNode=reverse1(node.next);//先反转后续节点node.next

        node.next.next=node;//将当前结点的指针域指向前一结点
        node.next=null;//前一结点的指针域令为null

        return newNode;
    }

    /**
     * 单链表检测环：快慢指针
     * @param head
     * @param <T>
     * @return
     */
    public <T> boolean checkRing(Node<T> head){
        if(head == null || head.next ==null) {
            return false;
        }
        Node<T> fast=head;
        Node<T> slow=head;
        while (fast!=null&&slow!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }

    /**
     * 两个有序链表合并：指针交替后移
     * @param n1
     * @param n2
     * @return
     */
    public Node<Integer> mergeTwoList(Node<Integer> n1,Node<Integer> n2){
        if(n1==null){
            return n2;
        }
        if(n2==null){
            return n1;
        }
        Node<Integer> head=new Node<Integer>(0);
        Node<Integer> curr=head;
        while (n1!=null&&n2!=null){
            if(n1.data<n2.data){
                curr.next=n1;
                n1=n1.next;
            }else {
                curr.next=n2;
                n2=n2.next;
            }
            curr=curr.next;
        }
        if(n1!=null){
            curr.next=n1;
        }
        if(n2!=null){
            curr.next=n2;
        }
        return head.next;
    }

    /**
     * 两个有序链表合并：递归
     * @param n1
     * @param n2
     * @return
     */
    public Node<Integer> mergeTwoList1(Node<Integer> n1,Node<Integer> n2){
        if(n1==null){
            return n2;
        }
        if(n2==null){
            return n1;
        }
        Node<Integer> head;
        if(n1.data<n2.data){
            head=n1;
            head.next=mergeTwoList1(n1.next,n2);
        }else {
            head=n2;
            head.next=mergeTwoList1(n1,n2.next);
        }
        return head;
    }

    /**
     * 链表中倒数第k个节点:笨办法，快慢指针
     * @param head
     * @param k
     * @param <T>
     * @return
     */
    public <T> Node<T> getKthFromEnd(Node<T> head, int k) {
        if(head==null){
            return head;
        }
        Node<T> fast=head;
        Node<T> slow=head;
        int slowCount=1;
        int fastCount=1;
        while(fast!=null&&slow!=null){
            if(slow.next!=null){
                slow=slow.next;
                slowCount++;
            }else{
                break;
            }

            if(fast.next!=null){
                if(fast.next.next!=null){
                    fast=fast.next.next;
                    fastCount=fastCount+2;
                }else{
                    fastCount++;
                    break;
                }
            }else{
                break;
            }
        }
        int index=fastCount-k+1-slowCount;
        if(index==0){
            return slow;
        }
        if(index>0){
            while(index>0){
                slow=slow.next;
                index--;
            }
            return slow;
        }
        else{
            index=fastCount-k+1;
            int i=1;
            slow=head;
            while(i<index){
                slow=slow.next;
                i++;
            }
            return slow;
        }

    }

    /**
     * 链表中倒数第k个节点:快慢指针
     * 1.快指针先走k步
     * 2.然后快慢指针一起走，直到快指针走出尾节点，指向尾节点的next
     * 思路：倒数k节点的位置=n-k+1。
     * 先走k步后，慢指针走n-k+1步，就是倒数k节点的位置
     * @param head
     * @param k
     * @param <T>
     * @return
     */
    public <T> Node<T> getKthFromEnd1(Node<T> head, int k) {
        if(head==null){
            return head;
        }
        Node<T> fast=head;
        Node<T> slow=head;
        int count=1;
        while(count<=k&&fast!=null){
            fast=fast.next;
            count++;
        }
        while(fast!=null){
            count++;
            fast=fast.next;
            slow=slow.next;
        }
        if(count<k){
            return null;
        }
        return slow;
    }

    /**
     * 删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。
     * 解题思路：把要删除的节点的值替换成next节点，然后把指针指向next节点的next节点。
     * 把要删除的节点变成next节点，然后抛弃掉原来的next节点。
     * @param node
     */
    public <T> void deleteNode(Node<T> node) {
        node.data=node.next.data;
        node.next=node.next.next;
    }

    public static class Node<T>{
        public T data;
        public Node<T> next;

        public Node(T t){
            data=t;
            next=null;
        }
    }
}
